package com.lh.demo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: linghao
 * @since: 2023/2/10
 *
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 变位词 指字母相同，但排列不同的字符串
 *
 * 剑指OfferII014字符串中的变位词滑动
 */
public class 剑指OfferII015字符串中的所有变位词 {

    //滑动窗口
    public List<Integer> findAnagrams(String s, String p) {
        int n=s.length(),m = p.length();
        List<Integer> list = new ArrayList<>();
        if(n<m)return list;
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];

        for(int i=0;i<m;i++){
            cnt1[s.charAt(i) - 'a']++; //-'a' 为对应到26个数组
            cnt2[p.charAt(i) - 'a']++;
        }

        if(Arrays.equals(cnt1,cnt2)){
            list.add(0);
        }

        //前进后出 滑动
        for(int i=m;i<n;i++){
            ++cnt1[s.charAt(i) - 'a'];
            --cnt1[s.charAt(i-m) - 'a'];
            if(Arrays.equals(cnt1,cnt2)){
                list.add(i-m+1);
            }
        }
        return list;
    }
}
